1. Field of the Invention
The present invention relates to encoders and decoders for telecommunication systems. In particular, it relates to address generation in encoders and decoders for third generation (and later) telecommunications systems such as the third generation Universal Mobile Telecommunications System (3G/UMTS).
2. Background of Related Art
Third Generation (3G) Universal Mobile Telecommunications System (UMTS) designs offer mobile operators significant capacity and broadband capabilities to support great numbers of voice and data customers—especially in urban centers.
3G/UMTS has been specified as an integrated solution for mobile voice and data with wide area coverage. Universally standardized via the Third Generation Partnership Project (www.3gpp.org) and using globally harmonized spectrum in paired and unpaired bands, 3G/UMTS in its initial phase offers theoretical bit rates of up to 384 kbps in high mobility situations, rising as high as 2 Mbps in stationary/nomadic user environments. Symmetry between uplink and downlink data rates when using paired (FDD) spectrum also means that 3G/UMTS is ideally suited for applications such as real-time video telephony—in contrast with other technologies such as Asynchronous Digital Subscriber Line (ADSL) where there is a pronounced asymmetry between uplink and downlink throughput rates.
Specified and implemented as an end-to-end mobile system, 3G/UMTS also features the additional benefits of automatic international roaming plus integral security and billing functions, allowing operators to migrate from 2G to 3G while retaining much of the existing core network. Offering increased capacity and speed at lower incremental cost as compared with second generation mobile systems, 3G/UMTS gives operators the flexibility to introduce new multimedia services to business users and consumers while providing an enhanced user experience. This in turn provides the opportunity for operators to build on the brand-based relationships they already enjoy with their customers—and drive new revenue opportunities by encouraging additional traffic, stimulating new usage patterns and strengthening customer loyalty.
Ongoing technical work within 3GPP will see further increases in throughput speeds of the WCDMA Radio Access Network (RAN). High Speed Downlink Packet Access (HSDPA) and High Speed Uplink Packet Access (HSUPA) technologies are already standardized and are undergoing network trials with operators in the Far East and North America. Promising theoretical downlink speeds as high as 14.0 Mbps (and respectively 5.8 Mbps uplink), these technologies will play an instrumental role in positioning 3G/UMTS as a key enabler for true ‘mobile broadband’. Offering data transmission speeds on the same order of magnitude as today's Ethernet-based networks that are a ubiquitous feature of the fixed-line environment, 3G/UMTS will offer enterprise customers and consumers all the benefits of broadband connectivity whilst on the move.
Third generation mobile radio systems such as W-CDMA and cdma2000 have adopted the use of turbo codes for channel coding due to their impressive performance. Previous turbo decoders had been developed for a single standard or for a fixed data rate, but flexible and programmable decoding is required for 3G communications because: 1) global roaming is recommended between different 3G standards, and 2) the frame size may change on a frame basis.
3G/UMTS systems include data encoders and decoders, and within the turbo encoder/decoder is a component called an interleaver address generator (IAG). The interleaver address generator is used to generate a sequence of data addresses for the encoding and/or decoding processes. The generated address sequence is used multiple times in a decoding process.
Interleavers make the implementation of a multi-standard turbo decoder difficult, as the operations and parameters of their generation rules are distinct and complex. Fortunately, the standards share the general concept of block interleavers that write data in a two-dimensional matrix row by row, permutes them, and reads them out column by column.
The current third generation partnership project (3GPP) UMTS cellular standard, (TS 25.212 V5.6 “Multiplexing and Channel Coding Specification”, 3GPP 2004) specifies an interleaver address pattern system for encoding and iterative turbo decoding. The turbo decoding process requires many iterations to produce a result. Each iteration that the turbo decoder runs can be considered in two parts—an H1 half-iteration where sequential addresses access the interleaver, and an H2 half-iteration where the generated interleaver address patterns access the interleaver. The 3GPP interleaver address pattern system produces a different address pattern for every possible block size, from length 40 to 5114 user information bits.
Interleaver address generators for 3GPP standards also have been implemented as lookup-tables where the address sequence for a particular block is computed off-chip. See Bickerstaff, M. et al., “A 24Mb/s Radix-4 LogMAP Turbo Decoder for 3GPP-HSDPA Mobile Wireless”, ISSCC 2003, paper 8.5, pp. 150-151. For instance, as explained in this reference, a software-based 3GPP turbo interleaver address generator simplifies the high complexity of the 3GPP turbo interleaving algorithm, resulting in decoders that use a large interleaver address table. The interleave address table is programmed by a host processor for each new block size (based on the current data rate, frame size, etc.) In a hardware IAG [e.g.: U.S. Pat. No. 6,851,039, U.S. patent appl. 20030221084], interleaver addresses are computed on the fly, enabling the decoder to switch block sizes quickly. This greatly reduces databus bandwidth (e.g., by a factor of 30), and computational load on the host, resulting in a more efficient multi-user system paritcularly for basestation applications.
FIG. 5 shows a conventional decoder turbo interleaver address processor architecture.
In particular, as shown in FIG. 5, the interleaver address processor architecture uses three small tables 502, 504, 506 to compute an interleaver address. The rj/rj+1 table 502 is a table of permuted prime integers implemented as a small combinatorial ROM. The T table 504, also implemented as a small combinatorial ROM, contains the inter-row permutation patterns. To change the turbo block size, the host or additional hardware populates a computed table 506 of base sequences for intra-row permutations (S table) with from 6 to 256 8-bit entries (block size dependent).
Due to the rectangular arrangement of interleave table, the specified IAG system can produce addresses that are outside the valid range of the related block size (e.g.: 2290 is outside the range for a block size of 2281). Such invalid addresses are typically removed from the generated sequence either by abandoning the invalid address and computing the correct address in the next clock cycle, or by replicating address computation hardware (with one engine generating address I, and the other engine generating the next address I+1 at the same time).
A conventional IAG can be trained to always produce a valid address sequence by performing a trial address generation during setup time to store row/column indexes of invalid (pruned) data addresses so it can avoid (or skip) these address during decoding, resulting in non-stop valid address generation. The IAG training starts in parallel with a 1st half-iteration decoding process. Without optimization, the IAG training needs a memory of 239 words with 10 bits in each word, and finishes later than the 1st half-iteration, thus causing a pause in each cycle of the decoding process. The result is slower decoding, use of more area, and higher power consumption.
Interleaver address generators for 3GPP standards have been implemented as ‘on-the-fly’ engines in an ASIC. See Bickerstaff, M. et al., “A Unified Turbo/Viterbi Channel Decoder for 3GPP Mobile Wireless in 0.18 um CMOS”, IEEE JSSC V37 N11, Nov. 2002. (invited paper from ISSCC 2002). See also Shin, M-C., Park, I-C., “A Programmable Turbo Decoder for Multiple 3G Wireless Standards”, ISSCC 2003, Paper 8.7, pp. 154-155.
A problem with an on-the-fly computation of interleaver addresses is referred to as “address pruning”, which refers to the discarding of invalid addresses. Address pruning occurs when the required block size is not an integer multiple of the number of columns in the interleaver table, as depicted in FIG. 6.
In particular, FIG. 6 depicts conventional third generation partnership project (3GPP) turbo interleaver address pruning. In this case, the interleaver algorithm can produce addresses which are unused, and it is necessary to perform another computation to compute the next address. The interleaver algorithm preferably guarantees that there will never be two consecutive unused addresses. Thus, for an on-the-fly design, generating one valid address per clock cycle can be guaranteed by running two regular hardware IAGs (without a training feature) side by side so that at least one valid address is always available. By implementing two interleaver data paths in parallel, it is possible to guarantee one valid interleaver address every clock cycle and hence not stall the decoder. However, replicating the interleaver address generator engines (to mitigate throughput reduction) increases power consumption, gate count and complexity, because of the need for a relatively large interleaver address table.
In a look-up table IAG design, a guaranteed valid address sequence is computed by a processor and stored in a memory table, but this requires CPU intervention, additional chip area, and relatively high power consumption. Also, the process of discarding invalid addresses reduces the total effective throughput of the decoder. Moreover, the decoding time is slower due to typically slow software address calculations and to the loading of an address table.
The present invention introduces a new, faster method for training an interleaver address generator (IAG), and an efficient data structure for storing invalid (i.e., pruned) addresses, while solving conventional problems of slower decoding, required use of more surface area, and higher power consumption.